package 剑指Offer._3140;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/10/29 9:30
 * 二叉搜索树的后序遍历序列
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
 * 算法：单调栈
 * 后序遍历：left --> right --> root
 * 逆后序遍历：root --> right --> left
 * 如果数组满足逆后序遍历，那么就返回 true
 * root 到 right 是单调递增的，可以使用单调栈来记录
 * 如果是右子树，则往单调栈里放，
 * 如果碰到当前元素小于栈顶元素，表示遍历到了左子树，就要将栈中元素大于该元素的弹出
 * 最后一个弹出的元素是当前元素的父节点
 */
public class _33 {

    public boolean verifyPostorder(int[] postorder) {
        Deque<Integer> stack = new ArrayDeque<>();
        int parentNum = Integer.MAX_VALUE;
        for (int i = postorder.length - 1; i >= 0; i--) {
            int n = postorder[i];
            if (n > parentNum) return false;
            // 最后一个弹出的元素是 n 的父节点
            while (!stack.isEmpty() && n < stack.peek()) parentNum = stack.pop();
            stack.push(n);
        }
        return true;
    }

}
